<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 用来保存链表子元素
        class Node {
            constructor(element) {
                this.element = element;
                this.next = null;
            }
        }

        // 链表
        class LinkedList {
            constructor() {
                this.head = null;
                this.length = 0;
            }
            // 添加元素
            append(element) {
                // 创建新的链表元素
                let node = new Node(element),
                    // 指针
                    current;
                // 如果没有链表头，该元素为表头
                if (this.head == null) {
                    this.head = node;
                } else {
                    // 有表头，遍历链表，把创建的链表元素添加到最后一项的next后面
                    current = this.head;
                    while (current.next != null) {
                        current = current.next;
                    }
                    current.next = node;
                }
                // 链表长度加1
                this.length++;
            }
            // 在指定位置移除元素
            removeAt(position) {
                if (position > -1 && position < this.length) {
                    let current = this.head,
                        index = 0,
                        prev;

                    if (position === 0) {

                        header = current.next;

                    } else {
                        while (index++ < position) {
                            prev = current;
                            current = current.next;
                        }
                        prev.next = current.next;
                    }
                    length--;
                    return current.element;
                } else {
                    return null;
                }
            }
            // 在任意位置插入一个元素
            insert(position, element) {
                // 注意这里可能会添加到最后，所以<=链表长度
                if (position > -1 && position <= this.length) {
                    let node = new Node(element),
                        current = this.head,
                        index = 0,
                        previous;

                    if (position === 0) {

                        this.head = node;
                        node.next = current;

                    } else {
                        while (index++ < position) {
                            previous = current;
                            current = current.next;
                        }
                        previous.next = node;
                        node.next = current;
                    }
                    this.length++;
                    return true;
                } else {
                    return false;
                }
            }

            // toString方法实现
            toString() {
                let string = '',
                    current = this.head;
                while (current != null) {
                    string += current.element.toString();
                    current = current.next;
                }

                return string;
            }

            // indexOf方法实现
            indexOf(element) {
                let index = 0,
                    current=this.head;

                while (current != null) {
                    if (element === current.element) {
                        return index;
                    }
                    index++;
                    current = current.next;
                }
                return -1;
            }

            // 移除指定元素
            remove(element){
                return this.removeAt(this.indexOf(element));
            }
            // 是否为空
            isEmpty(){
                return this.length === 0;
            }
            // 返回链表长度
            size(){
                return this.length;
            }
            // 获取链表头
            getHead(){
                return this.head;
            }
        }

        let list = new LinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.insert(3, 4);
        console.log(list);
        list.append('haha');
        console.log(list.toString());
        console.log(list.indexOf(3));
        console.log(list.remove(3));
        console.log(list);
    </script>
</body>

</html>